package day_2022_9_to_12.Day;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author haomin
 * @date 2022/11/14 22:31
 **/
public class Day70_Review {
    class Solution {
        public int findRepeatNumber(int[] nums) {
            int i = 0;
            while(i < nums.length){
                int m = nums[i];
                int n = nums[m];
                if(m == i) i++;
                else if(m == n) return m;
                else {
                    nums[i] = n;
                    nums[m] = m;
                }
            }
            return -1;
        }
    }

    class Solution2 {
        public boolean findNumberIn2DArray(int[][] matrix, int target) {
            if(matrix.length == 0 || matrix[0].length == 0) return false;
            int m = matrix.length, n = matrix[0].length;
            int i = 0, j = n-1;
            while(i < m && j >= 0){
                if(matrix[i][j] < target) i++;
                else if(matrix[i][j] > target) j--;
                else return true;
            }
            return false;
        }
    }

    class Solution3 {
        public String replaceSpace(String s) {
            StringBuffer sb = new StringBuffer();
            for(int i = 0; i < s.length(); ++i){
                char c = s.charAt(i);
                if(c == ' ') sb.append("%20");
                else sb.append(c);
            }
            return sb.toString();
        }
    }

    class Solution4 {
        public int[] reversePrint(ListNode head) {
            Deque<Integer> s = new LinkedList<>();
            while(head != null) {
                s.push(head.val);
                head = head.next;
            }
            return s.stream().mapToInt(Integer::intValue).toArray();
        }
    }


    class Solution5 {
        public TreeNode buildTree(int[] preorder, int[] inorder) {
            return create(preorder, inorder, 0, inorder.length-1);
        }
        int i = 0;
        private TreeNode create(int[] pre, int[] in, int l, int r) {
            if(i == in.length) return null;
            if(l > r) return null;
            TreeNode cur = new TreeNode(pre[i]);
            int ind = findInd(cur.val, in);
            i++;
            cur.left = create(pre, in, l, ind - 1);
            cur.right = create(pre, in, ind + 1, r);
            return cur;
        }
        private int findInd(int value, int[] in){
            for(int i = 0; i < in.length; ++i) {
                if(value == in[i]) return i;
            }
            return -1;
        }
    }

    class CQueue6 {
        Deque<Integer> s1;
        Deque<Integer> s2;

        public void CQueue() {
            s1 = new LinkedList<>();
            s2 = new LinkedList<>();
        }

        public void appendTail(int value) {
            s1.push(value);
        }

        public int deleteHead() {
            if(!s2.isEmpty()) return s2.pop();
            else {
                while(!s1.isEmpty()) s2.push(s1.pop());
                return s2.isEmpty() ? -1 : s2.pop();
            }
        }
    }

    class Solution7 {
        int mod = (int)1e9 + 7;
        public int fib(int n) {
            if(n < 3) return n == 0 ? 0 : 1;
            int[] dp = new int[n+1];
            dp[1] = 1;
            for(int i = 2; i <= n; ++i) {
                dp[i] = (dp[i-1] + dp[i-2]) % mod;
            }
            return dp[n];
        }
    }

    class Solution8 {
        int mod = (int)1e9 + 7;
        public int numWays(int n) {
            if(n < 2) return 1;
            int[] dp = new int[n + 1];
            dp[1] = 1; dp[2] = 2;
            for(int i = 3; i <= n; ++i){
                dp[i] = (dp[i-1] + dp[i-2]) % mod;
            }
            return dp[n];
        }
    }

    class Solution9 {
        public int minArray(int[] numbers) {
            int l = 0, r = numbers.length - 1, mid;
            while(l <= r) {
                mid = l + ((r-l) >> 1);
                if(numbers[mid] < numbers[r]) {
                    r = mid;
                }else if(numbers[mid] > numbers[r]) {
                    l = mid + 1;
                }else r--;
            }
            return numbers[l];
        }
    }
}